class Solution:
    def diffWaysToCompute(self, s: str) -> int:
        stack = []
        nowNum = 0
        hadNum = False
        for i in range(len(s)):
            if s[i] in '0123456789':
                nowNum = nowNum * 10 + int(s[i])
                hadNum = True
            elif s[i] in '-+*/':
                if hadNum:
                    stack.append(nowNum)
                    nowNum = 0
                stack.append(s[i])
                hadNum = False
        if hadNum:
            stack.append(nowNum)
        result = self.opt(stack)
        return result

    def opt(self, stack):
        result = []
        if len(stack) == 1:
            result.append(stack[0])
            return result
        for i in range(1, len(stack), 2):
            r1 = self.opt(stack[0:i])
            r2 = self.opt(stack[i + 1:])
            for n1 in r1:
                for n2 in r2:
                    result.append(self.optNum(stack[i], n1, n2))
        return result

    def optNum(self, o, r1, r2):
        if o == '+':
            return r1 + r2
        elif o == '-':
            return r1 - r2
        else:
            return r1 * r2


if __name__ == '__main__':
    so = Solution()
    s = "2*3-4*5"
    r = so.diffWaysToCompute(s)
    print(r)
